/**
* 如果在插入排序中，我们不适用哨兵，而是使用“h”中的“1”来代替，这就变成了*h-sorts的程序。外循时改变增量序列，在这里我们使用的增量序列是 1 4 13 40 *121 364 1093 3280 9841 .....
*
*/
#include <stdio.h>
#include <stdlib.h>

//考虑移植性的问题，才把类型都定义为Item，这就可以随时改为浮点float都可以
typedef int Item;

#define key(A) (A)
//使用宏的一个好处，不用考虑参数的类型
#define less(A, B) (key(A) < key(B))
#define exch(A, B)  \
    {               \
	Item t = A; \
	A = B;      \
	B = t;      \
    }
#define compexch(A, B) \
    if(less(B, A))     \
    exch(A, B)
void shellsort(Item a[], int l, int r)
{ 
	int i,j,h;
	for(h=1;h<=(r-1)/9;h=3*h+1);
	for(;h>0;h/=3)
		for(i=l+h;i<r;i++){
			int j=i; Item v=a[i];
			while(j>=l+h && less(v,a[j-h])){
				a[j] = a[j-h];
				j-=h;
			}
			a[j] = v;	
		}
}

main(int argc, char* argv[])
{
	printf("Shellsort Method\n");
    int i, N = atoi(argv[1]), sw = atoi(argv[2]),j=0;
    int* a = malloc(N * sizeof(int));
	printf("%d items\n",N);
    if(sw)
	for(i = 0; i < N; i++) {
	    a[i] = 1000 * (1.0 * rand() / RAND_MAX);
		printf("%d item is %d\n",i,a[i]);
	}
    else
/** 不知道是不是我的知识不够，书本上的例子这段代码运行不起来
	while(scanf("%d", &a[N]) == 1)
	    N++; 
		 */
	while(j<N){
		scanf("%d",&a[j++]);
	}
	//2.调用希尔排序的函数对这些整型进行排序
	
	int h;
	for(h=1;h<=(N-1-1)/9;h=3*h+1);
	printf("Uses sequences is:"); //Uses sequences is:265720 88573 29524 9841 3280 1093 364 121 40 13 4 1
	for(;h>0;h/=3)
		printf("%d ",h);
	printf("\n");
	
    shellsort(a, 0, N - 1);
	//3.输出排序后的结果
    for(i = 0; i < N; i++)
		printf("%5d", a[i]);
    printf("\n");
}
